1. Field of the Invention
An apparatus, system, method and computer program product for private ranging between at least two devices in radio communications with each other. In particular, an apparatus, system, method and computer program product for private ranging between at least two devices communicating via ultra wideband (UWB) protocols.
2. Background of the Invention
There is a growing demand for location awareness in short range radio networks, particularly UWT networks. Location awareness implies that the location of the devices is known. Typically, the location of the devices becomes known using radio ranging.
UWB or, digital pulse wireless is a wireless technology for transmitting large amounts of digital data over a wide spectrum of frequency bands with very low power for a short distance. Ultra wideband radio signals not only can carry a huge amount of data over a distance up to 230 feet at very low power (less than 0.5 milliwatts), but have the ability to carry signals through doors and other obstacles that tend to reflect signals having more limited bandwidths and a higher power.
Ultra wideband signals are broadcast concurrently as digital pulses that are timed very precisely on a carrier signal across a very wide spectrum of frequencies. A transmitter and a receiver are synchronized to send and receive pulses with an accuracy of trillionths of a second. On any particular frequency, the ultra wideband signal has less power than normal and anticipated background noise. Theoretically, interference with conventional radio signals is negligible.
Ultra wideband communication has two main types of application:                Applications involving radar, in which the signal penetrates nearby surfaces but is reflected by surfaces that are farther away, allowing objects to be detected behind walls or other coverings.        Voice and data transmission application, in which digital pulses allow a very low powered and relatively low cost signal to carry information at very high data rates over a short range.In the U.S., the Federal Communications Commission approved the commercial use of ultra wideband signals on Feb. 14, 2002.        
UWB applications communicate in accordance with a protocol stack as shown in FIG. 1. Here a device 101 is in communication with a device 102 via wireless link 100. The protocol for the communications in each device includes a physical layer (PHY) 110, a media access control (MAC) layer 120, a network layer 130, a transport layer 140, a session layer 150, a presentation layer 160, and an application layer 170.
As shown in FIG. 2, conventional UWB two-way ranging may be performed by two devices. Conventionally, a range packet (230) is first sent from a device A (210) to a device B (220). Upon receipt at the device B (220), a range packet (240) is returned to device A (210).
FIG. 3 provides more details about the two-way ranging described relative to FIG. 2. Again, the two devices 210 and 220 are in communication with each other. The first device 210 includes an originator media access controller 410 which sends a range request 450 to an originator physical controller 420. This range request causes the originator physical controller 420 to send a range packet 230 to the receiving device 220. Within the receiving device 220, a receiving device physical layer controller 430 receives the range packet 230, the range packet 230 is processed during a turn around time 455, and a response range packet 240 is sent to the first device 210. This response range packet 420 is received by the originator physical layer controller 240. The originator physical controller 420 sends a range confirmation signal 460 to the originator media access controller 410.
As a specific example, consider a time-of-arrival (TOA) based ranging system. First at the MAC layer of the originator, A, the range request is generated and passed to the PHY layer. Then, the PHY transmits the range packet to the device 220. The device 220 receives the range packet and sends the response packet 240 to device A. Assume that the elapsed time between the departure time of A's message and the arrival time of the reply from device 220 at device 210 is Tr. The time Tr can be approximated as Tr=2Tf+Tta, where Tf is the one way time of flight of the signal and Tta is the turn around time 455, the time difference between the reception timestamp of signal at device 220 and the departure timestamp of reply from device 220. Typically, each wireless packet (or message) includes a preamble, a MAC header and a payload. When a packet is received, the processing of the preamble is done first for acquisition, synchronization and ranging. Then, the rest of the packet is passed to the MAC layer. In order to decrease a positive bias in the ranging error due to Tta, device 220 can process the preamble of a received message at its physical (PHY) layer, and reply to the range packet before passing the header and the payload to the MAC layer. This minimizes the turn around time 455. However, such a step imposes a vulnerability for device 220, because the response reveals the range to device 210 without knowing whether device 210 is an authentic device. On the other hand, if device 220 withholds its reply until its MAC layer authenticates device 210, the turn around time becomes undesirably long. Thus, what is desired, as discovered by the present inventors, is an apparatus, system, method and computer program product for private ranging between at least two devices communicating via ultra wideband (UWB) protocols.
To meet the need for improved and private location awareness in UWB, an IEEE 802.15.4a Task Group (TG) has been established to develop a UWB-based physical (PHY) layer standard with a precision ranging capability. An UWB signal has a relative bandwidth larger than 20% or absolute bandwidth of at least 500 MHz. One type of an UWB system is an impulse radio (IR). IR uses extremely short duration pulses to generate signal waveforms, and allows fine time resolution of channel multipath characteristics, which is important in identifying the line of sight signal for precision ranging. If a ranging process does not involve MAC layers, then the process is called fast ranging.
In UWB ranging, the goal is to accurately estimate the distance between two devices. In a paper by J-Y. Lee and R. A. Scholtz, “Ranging in a dense multipath environment using an UWB radio link,” IEEE Trans. Select Areas in Communications, vol. 20, issue 9, pp. 1677-1683, December 2002, the entire contents of which is incorporated by reference, a time-of-arrival (TOA)-based ranging scheme using an ultra-wideband (UWB) radio link is described. That ranging scheme implements a search process for the detection of a direct path signal in the presence of dense multipath, utilizing generalized maximum-likelihood (GML) estimation. Models for critical parameters in the process are based on statistical analysis of propagation data. The process is tested on another independent set of propagation measurements. That UWB ranging system uses a correlator and a parallel sampler with a high-speed measurement capability in the transceiver to accomplish two-way ranging in the absence of synchronized clocks.
In a paper by S. Gezici, Z. Tian, G. B. Giannakis, H. Kobayashi, A. M. Molisch, H. V Poor, Z. Sahinoglu, “Localization Via UWB Radios,” IEEE Signal Pro. Magazine, v.22, n. 4, pp. 70-84, July 2005, the entire contents of which is incorporated by reference, localization techniques relying on wireless ultra-wideband (UWB) signaling are described. Various localization alternatives are considered and the UWB time-of-arrival based one is found to have a highest ranging accuracy.
The challenges in UWB positioning problems, such as multiple-access interference, multipath and non-line-of-sight propagation are presented along with the fundamental limits for time-of-arrival estimation and time-of-arrival-based positioning. To reduce the complexity of optimal schemes achieving those limits, suboptimal alternatives have been developed and analyzed. Moreover, a hybrid scheme that incorporates time-of-arrival and signal strength measurements is known investigated.
In the prior art, mainly signal waveform design and development of signal edge detection techniques have been described. Also various range measurement techniques are available. The two well-studied are Time of Arrival (TOA) and Time Difference of Arrival (TDOA). The TOA requires an exchange of a pair of messages between two devices to eliminate clock offsets, while the TDOA relies on arrival-time differences of messages from two sources. The accuracy of a range estimate depends on the speed at which the message exchanges occur. It is typical for a ranging system to have a very fast response to a message at the receiving device due to a small fast around time. However, this ability to have a fast turn around time poses many design problems, where one of these design problems concerns security.
Patent Publication No. 2005/0166040 describes a method for enabling secure communications between multiple devices. That document describes a method for generating and sending a message from a first device. The method includes the steps of: determining a message including an action; generating an authentication code on the basis of the action and a parameter, the parameter being indicative of an attribute of the action; and sending the message and authentication code from the first entity. The method maps various actions to various parameters, and then an authentication code is assigned to the parameters. However, for private ranging, authentication alone is insufficient, because message exchanges happen between the physical layers of involved devices.
Patent Publication No. 2005/0073433 describes precision measuring collision avoidance system and refers to two-way message exchanges for distance estimation. However, that document does not address security or any means to decrease the turn around time.
Patent Publication No. 2005/0078626 describes a method and system for detecting the position of a mobile unit in a multi-path environment. The document describes an order of message flows between mobile stations, a server and a base station, and wireless communication means. The base station sends a wireless signal to the wireless communication means requesting the transmission of a specific wireless signal. The wireless communication means sends a wireless signal in response to this request to the base station. The method obtains different signals with multi-path characteristics on receivers by a wireless receiver capable of sending and receiving to and from different antenna positions used by the mobile stations and by measuring the timing of wireless signals exchanged among the base station and the wireless receivers. However, that document does not address security aspects in ranging.
Patent Publication No. 2003/0076239 describes a method for locating moving objects. At least one interrogator arranged in a stationary position relative to a path of movement of an object, and the interrogator transmits an electromagnetic signal within a reading range. The moving object carries at least one transponder, which transmits a response signal to the transmitted signal. The interrogator receives and evaluates the response signal. The transponder's response signal contains information identifying the transponder. However, that document does not address security aspects in ranging.
Patent Publication No. 2002/0097184 describes a method in which the location of a radio frequency emitting target device, in absolute or relative GPS coordinates, from a single airborne platform is determined. The method is shown to prevent single and multiple GPS jammers from being able to jam conventional GPS signals. The method uses a signal processing technique, which emulates an antenna moving at very high velocities to induce a virtual Doppler shift on signals incident upon a linear antenna array, and relates the virtual Doppler shift to the signal direction of arrival. That method prevents jamming during GPS based positioning. However, that document does not describe private ranging.
Patent Publication No. 2005/0136892 describes a system and method providing secure authentication of a wireless communication channel for a vehicle telematics device that includes detecting a wireless access point within radio range of a telematics device, requesting authentication information for the access point through a first secure communication channel to a call center, receiving authentication information for the wireless access point from the call center through the first secure communication channel, and providing authentication information for the telematics device to the wireless access point through a second secure communication channel. However, that approach requires the use of specially established secure channels, thus incurring an operational overhead complexity and expense.
Patent Publication No. 2004/0209598 describes a method and apparatus for establishing secure wireless links between a handset and a base station in a wireless telephone systems. The method for generating a secure wireless link between a handset and a base station includes initiating a linking procedure, generating a security code, displaying the security code at the base station, entering the security code into the handset and then establishing a radio frequency link between the handset and the base station utilizing the security code. However, that method requires direct user involvement and does not provide for private ranging.
Patent Publication No. 2003/0139190 describes a method and apparatus for providing authenticated, secure, communication between a gaming host communicating via radio frequency (RF) sub-carriers to a remote user device in another location. Location of the remote user device and the host server are determined by accessing signals generated by either Global Positioning System (GPS) satellites, or by terrestrial radio broadcast stations, through a process known as radio frequency trilateration. Player authentication (identity verification) is determined by use of a personal identification number. In GPS based positioning, a GPS receiver receives signals from multiple satellites. Each satellite transmits a unique signal assigned to it so-called signature. The signature consists of pseudo-random noise (PRN) code. That unique identifier is repeated and serves the purposes of identification and signal transit time measurement. Any receiver receives the same signal from the same satellite. GPS does not vary the waveform from a ranging operation to another. In GPS, messages are not exchanged, and signal transmission is one-way from the satellites to the receivers. Thus, GPS does not support two-way ranging.